package _08_DFS_BFS;

import java.util.LinkedList;
import java.util.Queue;

public class _1091_二进制矩阵中的最短路径 {

    public static void main(String[] args) {
        _1091_二进制矩阵中的最短路径 v = new _1091_二进制矩阵中的最短路径();
        int[][] ins = new int[][]{
                {0, 1, 0, 0, 1, 1, 0},
                {1, 0, 0, 0, 0, 0, 0},
                {1, 0, 0, 1, 1, 1, 1},
                {0, 1, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 0, 0, 1, 0, 0, 0},
                {1, 0, 1, 0, 0, 1, 0},
        };
        System.out.println(v.shortestPathBinaryMatrix(ins));
    }

    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] == 1) return -1;
        int[][] vertex = new int[][]{
                {1, 0},
                {-1, 0},
                {0, 1},
                {0, -1},
                {1, 1},
                {1, -1},
                {-1, 1},
                {-1, -1},
        };
        Queue<int[]> queue = new LinkedList<>();
        int n = grid.length;
        // 放入起点
        queue.offer(new int[]{0, 0});
        grid[0][0] = 1;
        int path = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                // 遍历完这层
                int[] node = queue.poll();
                int row = node[0];
                int col = node[1];
                if (row == n - 1 && col == n - 1) {
                    return path;
                }
                // 当前访问的节点变为1
                for (int[] ints : vertex) {
                    int newRow = row + ints[0];
                    int newCol = col + ints[1];
                    if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] == 0) {
                        queue.offer(new int[]{newRow, newCol});
                        grid[newRow][newCol] = 1;
                    }
                }
            }
            path++;
        }
        return -1;
    }


    // 使用BFS层序遍历，第一个向遍历到的，一定是最短的路径, 使用额外数据保存层数
    public int shortestPathBinaryMatrix1(int[][] grid) {
        if (grid[0][0] == 1) return -1;
        int[][] vertex = new int[][]{
                {1, 0},
                {-1, 0},
                {0, 1},
                {0, -1},
                {1, 1},
                {1, -1},
                {-1, 1},
                {-1, -1},
        };
        Queue<int[]> queue = new LinkedList<>();
        int n = grid.length;
        // 放入起点
        queue.offer(new int[]{0, 0, 1});
        grid[0][0] = 1;
        while (!queue.isEmpty()) {
            // 能进入此，路径一定不为1
            int[] node = queue.poll();
            int row = node[0];
            int col = node[1];
            int level = node[2];
            if (row == n - 1 && col == n - 1) {
                return level;
            }
            // 当前访问的节点变为1
            for (int[] ints : vertex) {
                int newRow = row + ints[0];
                int newCol = col + ints[1];
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n && grid[newRow][newCol] == 0) {
                    queue.offer(new int[]{newRow, newCol, level + 1});
                    grid[newRow][newCol] = 1;
                }
            }
        }
        return -1;
    }

}
